package com.sise.BFS;

import com.sise.Tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 *      广度优先遍历简称 BFS（Breadth First Search）
 *
 *      参考链接：https://labuladong.gitbook.io/algo/bi-du-wen-zhang/bfs-kuang-jia
 *
 *      解题套路：BFS 的核心思想应该不难理解的，就是把一些问题抽象成图，从一个点开始，向四周开始扩散。
 *              一般来说，我们写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。
 *
 *      // 计算从起点 start 到终点 target 的最近距离
 *      int BFS(Node start, Node target) {
 *          Queue<Node> q; // 核心数据结构 - 队列
 *          Set<Node> visited; // 避免走回头路
 *
 *          q.offer(start); // 将起点加入队列
 *          visited.add(start); // 将走过的路记录起来
 *          int step = 0; // 记录扩散的步数
 *
 *          // 当队列不为空时
 *          while (q not empty) {
 *              int sz = q.size();
 *              // 将当前队列中的所有节点向四周扩散
 *              for (int i = 0; i < sz; i++) {
 *                  Node cur = q.poll();
 *                  // 划重点：这里判断是否到达终点
 *                  if (cur is target)
 *                      return step;
 *                  // 将 cur 的相邻节点加入队列
 *                  for (Node x : cur.adj())
 *                      if (x not in visited) {
 *                          q.offer(x);
 *                          visited.add(x);
 *                      }
 *              }
 *              // 划重点：更新步数在这里
 *              step++;
 *          }
 *      }
 */
public class BFS {

    /**
     *      例子：求二叉树的最小深度
     *
     *      queue.offer() 的底层实现是 add()
     *      queue.poll()  删除
     */
    int minDepth(TreeNode root) {

        // 如果当前节点为空，那么就返回层数 0
        if (root == null) return 0;
        // 创建队列，作为 BFS 的核心辅助工具。这里要注意的是，每次递归的时候，队列都会重新创建一个，故此不会 污染到其他队列的情况
        Queue<TreeNode> queue = new LinkedList<>();
        // 将入参结点加入队列
        queue.offer(root);
        // 记录 BFS 走过的路；root 本身就是一层，故此 depth 初始化为 1
        int depth = 1;

        // 当队列不为空时
        while (!queue.isEmpty()){
            // 计算当前队列的长度，因为这里是 while 循环，第一次遍历的是头结点，将其左右子节点加入（有可能只有一个节点）
            // 接着遍历 头节点的下一层， 使用 size 控制遍历的个数，
            // 保证了每一次的遍历都是 一整层，不会遍历到下一层，直到第一颗 左右节点都为空的树，此时返回 最小深度
            int size = queue.size();

            for (int i = 0; i < size; i++){
                TreeNode poll = queue.poll();
                if (poll.left == null && poll.right == null){
                    return depth;
                }

                // 将 本节点 的相邻节点加入队列
                if (poll.left != null){
                    queue.offer(poll.left);
                }
                if (poll.right != null){
                    queue.offer(poll.right);
                }
            }
            // 增加层数（步数） 当一整层的节点都遍历结束后，进入下一层前（重新获取 queue 的个数），才将深度 + 1
            depth++;
        }
        return depth;
    }
}
